//
// Created by isabella on 25-6-4.
//
#include <Sort.h>

vector<int> CountingSort::sort(vector<int> nums) {
    vector<int> counting(16, 0);
    int max_value = 0;
    for (int i = 0; i < nums.size(); i++) {
        max_value = max_value > nums[i] ? max_value : nums[i];
        while (nums[i] >= counting.size()) {
            counting.reserve(counting.size() *2);
        }
        counting[nums[i]]++;
    }
    vector<int> pre_sum(max_value, 0);
    pre_sum[0]=counting[0];
    for (int i = 1; i <= max_value; i++) {
        pre_sum[i] = pre_sum[i-1] + counting[i];
    }
    vector<int> result(nums.size(), 0);
    for (int num : nums) {
        result[pre_sum[num]-1] = num;
        pre_sum[num]--;
    }
    return result;
}
